import java.util.*;

public class Solution127 {

    static class Pair{
        String s;
        int step;

        public Pair(String s, int step) {
            this.s = s;
            this.step = step;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String,Integer> map=new HashMap<>();
        for (String s : wordList) {
            map.put(s,Integer.MAX_VALUE);
        }
        if (!map.containsKey(endWord)){
            return 0;
        }
        map.put(beginWord,1);
        Queue<Pair> queue=new LinkedList<>();
        queue.offer(new Pair(beginWord, 1));
        while (!queue.isEmpty()){
            Pair pair=queue.poll();
            for (int i=0;i<pair.s.length();i++){
                StringBuilder stringBuilder=new StringBuilder(pair.s);
                for (int j=0;j<26;j++){
                    stringBuilder.setCharAt(i,(char)(j+'a'));
                    if (map.getOrDefault(stringBuilder.toString(),0)==Integer.MAX_VALUE){
                        map.put(stringBuilder.toString(),pair.step+1);
                        queue.offer(new Pair(stringBuilder.toString(), pair.step + 1));
                    }
                }
            }
        }
        return map.get(endWord)==Integer.MAX_VALUE?0:map.get(endWord);
    }

    public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        list.add("hot");list.add("dot");list.add("dog");list.add("lot");list.add("log");list.add("cog");
        System.out.println(new Solution127().ladderLength("hit","cog",list));
    }
}
